#include <bits/stdc++.h>

using namespace std;

class Solution{
public:
    int minimumSumSubarray(vector<int>& nums, int l,int r){
        int n=nums.size(); const int INF=1e9; int ans=INF;
        for(int len=l;len<=r;len++){
            for(int i=0;i+len<=n;i++){
                int tmp=0;
                for(int j=0;j<len;j++) tmp+=nums[i+j];
                if(tmp>0) ans=min(ans,tmp);
            }
        }
        return ans<INF?ans:-1;
    }
};

class Solution2{
public:
    bool isPossible(string s, string t, int k){
        int n=s.size(); unordered_map<string,int>mp; int len=n/k;
        for(int i=0;i<n;i+=len)mp[s.substr(i,len)]++;
        for(int i=0;i<n;i+=len)mp[s.substr(i,len)]--;
        for(auto &p:mp)if(p.second!=0) return false;
        return true;
    }
};

class Solution3{
public:
    int minArr(vector<int>& nums, int k, int op1, int op2){
        int n = nums.size();
        vector memo(n, vector(op1 + 1, vector<int>(op2 + 1, -1))); // -1 表示没有计算过
        auto dfs = [&](auto&& dfs, int i, int op1, int op2) -> int {
            if (i < 0) {
                return 0;
            }
            int& res = memo[i][op1][op2]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }
            int x = nums[i];
            res = dfs(dfs, i - 1, op1, op2) + x;
            if (op1) {
                res = min(res, dfs(dfs, i - 1, op1 - 1, op2) + (x + 1) / 2);
            }
            if (op2 && x >= k) {
                res = min(res, dfs(dfs, i - 1, op1, op2 - 1) + x - k);
                if (op1) {
                    int y = (x + 1) / 2 >= k ? (x + 1) / 2 - k : (x - k + 1) / 2;
                    res = min(res, dfs(dfs, i - 1, op1 - 1, op2 - 1) + y);
                }
            }
            return res;
        };
        return dfs(dfs, n - 1, op1, op2);
    }
};

class Solution4{
public:
    long long maximizeSum(vector<vector<int>>& edges, int k){
        vector<vector<pair<int,int>>> g(edges.size()+1);
        long long sum_wt=0;
        for(auto& e: edges){
            int x=e[0], y=e[1], wt=e[2];
            g[x].emplace_back(y, wt);
            g[y].emplace_back(x, wt);
            sum_wt+=wt;
        }
        bool simple=true;
        for(auto& to: g){
            if(to.size()>k){
                simple=false;
                break;
            }
        }
        if(simple) return sum_wt;
        function<pair<long long, long long>(int, int)> dfs=[&](int x,int fa)->pair<long long, long long>{
            long long not_choose=0; vector<int> inc;
            for(auto& [y, wt]: g[x]){
                if(y==fa) continue;
                auto[nc, c]=dfs(y,x);
                not_choose+=nc;
                int d=c+wt-nc;
                if(d>0) inc.push_back(d);
            }
            sort(inc.begin(), inc.end(), greater());
            for(int i=0;i<min((int)inc.size(),k-1);i++){
                not_choose+=inc[i];
            }
            long long choose=not_choose;
            if(inc.size()>=k) not_choose+=inc[k-1];
            return {not_choose, choose};
        };
        return dfs(0,-1).first;
    }
};

int main(){
    vector<int> nums={3,-2,1,4};
    Solution s; cout<<s.minimumSumSubarray(nums, 2, 3)<<endl;
    Solution2 s2; cout<<s2.isPossible("abcd","cdab",2)<<endl;
    vector<int> nums3={2,8,3,19,3};
    Solution3 s3; cout<<s3.minArr(nums3, 3, 1,1)<<endl;
    vector<vector<int>> edges={{0,1,4},{0,2,2},{2,3,12},{2,4,6}};
    Solution4 s4; cout<<s4.maximizeSum(edges, 2)<<endl;

}